package leetcode_周赛._2023._12;

import java.util.HashMap;
import java.util.Map;

/**
 * 第 375 场周赛
 * AC_3
 *
 * @author yezh
 * @date 2023/12/10 16:47
 */
public class _10 {

    /**
     * 2962.统计最大元素出现至少 K 次的子数组
     * 算法: 滑动窗口
     * 枚举右端点, 移动左端点, left 是合法左端点的最大值
     */
    public long countSubarrays(int[] nums, int k) {
        int max = nums[0];
        for (int num : nums) max = Math.max(max, num);
        long ans = 0;
        for (int l = 0, r = 0, cnt = 0; r < nums.length; r++) {
            if (nums[r] == max) ++cnt;
            while (cnt >= k) {
                if (nums[l] == max) --cnt;
                ++l;
            }
            ans += l;
        }
        return ans;
    }


    /**
     * 2963.统计好分割方案的数目
     * 算法： 哈希表 + 合并区间
     */
    public int numberOfGoodPartitions(int[] nums) {
        int cnt = 0, mod = (int) (1e9 + 7), n = nums.length;
        // 找到可以切割的位置, m = 可切割的数量
        // 切割数 = 2 ^ m, 每个位置都有两种选项 - 切或不切
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) map.put(nums[i], i);
        for (int i = 0, maxIdx = 0; i < n; i++) {
            maxIdx = Math.max(maxIdx, map.get(nums[i]));
            if (i == maxIdx) ++cnt;
        }
        int ans = 1;
        System.out.println(cnt);
        // 这里减 1, 是因为 cnt 中包括了最后一个元素的位置, 而这个位置不需要考虑
        for (int i = 0; i < cnt - 1; i++) ans = (ans * 2) % mod;
        return ans;
    }

}
